package org.example.leetcpde;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class fourSum
        implements IArray {
    @Test
    void fourSum() {
                int[] nums = parse("[0,0,0,0]");
//        int[] nums = parse("[1,0,-1,0,-2,2]");
        List<List<Integer>> lists = fourSum(nums, 0);
        System.out.println(lists);
    }

    public List<List<Integer>> fourSum(int[] nums,
                                       int target) {
        if (nums == null || nums.length < 4) {
            return Collections.emptyList();
        }

        Arrays.sort(nums);

        int len = nums.length;
        int v1 = Integer.MAX_VALUE, v2 = v1, v3 = v1, v4 = v1;
        long sum = 0;
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < len - 3; i++) {
            if (i > 0 && nums[i] == v1) {
                continue;
            }
            v1 = nums[i];

            for (int j = i + 1; j < len - 2; j++) {
                if (j > i + 1 && nums[j] == v2) {
                    continue;
                }
                v2 = nums[j];

                for (int m = j + 1, n = len - 1; m < len - 1 && m < n; ) {
                    v3 = nums[m];
                    v4 = nums[n];
                    sum = (long) v1 + v2 + v3 + v4;
                    if (sum == target) {
                        res.add(List.of(v1, v2, v3, v4));
                    }

                    if (sum > target) {
                        do {
                            n--;
                        } while (nums[n] == v4 && m < n);
                    } else {
                        do {
                            m++;
                        } while (nums[m] == v3 && m < n);
                    }
                }
            }
        }

        return res;
    }
}
